// 《围棋》作者版权所有。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 垃圾收集器：堆栈对象和堆栈跟踪
// 参见https:
// 另见第22350期。

// 堆栈跟踪解决了确定
// 堆栈的哪些部分是活动的，应该进行扫描的问题。它作为扫描
// 单个goroutine堆栈的一部分运行。
// 
// 通常很容易静态确定堆栈的哪些部分是活动的，因为用户代码对堆栈变量有显式引用（读取和写入）。编译器可以进行简单的数据流
// 分析，以确定
// 代码中每个点的堆栈变量的活跃度。请参见cmd/compile/internal/gc/plive。进行分析。
// 
// 然而，当我们获取堆栈变量的地址时，确定
// 该变量是否仍然有效就不那么清楚了。我们仍然可以
// 寻找静态访问，但是通过指向
// 变量的指针进行的访问通常很难静态跟踪。指针
// 可以在堆栈上的函数之间传递，条件保留，
// 等等。
// 
// 相反，我们将动态跟踪指向堆栈变量的指针。
// 所有指向堆栈分配变量的指针都将位于
// 堆栈的某个位置（或在相关位置，如延迟记录），因此
// 我们可以高效地找到它们。
// 
// 堆栈跟踪被组织为一个小型垃圾收集跟踪
// 过程。此垃圾收集中的对象都是堆栈上的变量
// ，其地址已被获取，并且其本身包含一个
// 指针。我们称这些变量为“堆栈对象”。
// 
// 我们首先确定堆栈上的所有堆栈对象，以及所有
// 可能指向堆栈的静态活动指针。然后我们处理每个指针，看看它是否指向堆栈对象。如果是
// 则扫描堆栈对象。它可能包含指向
// 堆的指针，在这种情况下，这些指针被传递到主垃圾
// 集合。它还可能包含堆栈中的指针，在这种情况下，我们将它们添加到堆栈指针集中。
// 
// 一旦我们处理完所有指针（包括我们在处理过程中添加的指针），我们就找到了
// 处于活动状态的所有堆栈对象。任何死堆栈对象都不会被扫描，其内容
// 将不会使堆对象保持活动状态。与主要垃圾
// 收集不同，我们不能清除死堆栈对象；它们在死气沉沉的状态下生存，直到包含它们的堆栈框架被弹出。CDCDEFG
// /|+------+（124？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？| | | 
// /| | D---------/
// /|+--------+|第三部分，第四部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分，第三部分：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：CDEFG
// foo（）调用bar（）调用baz（）。每个在堆栈上都有一个框架。
// foo（）有堆栈对象A和B。
// bar（）有堆栈对象C和D，C指向D，D指向A。
// baz（）有堆栈对象E指向C，局部变量F指向E。
// 
// 从局部变量F中的指针开始，我们最终将
// 扫描所有的E、C、D，和A（按顺序）。B永远不会被扫描
// 因为没有指向它的活动指针。如果B也是静态
// dead（这意味着foo（）在调用
// bar（）后再也不会访问B），那么B进入堆的指针就不会被认为是活动的。

package runtime

import (
	"internal/goarch"
	"unsafe"
)

const stackTraceDebug = false

// 堆栈跟踪期间找到的指针的缓冲区。
// 必须小于或等于workbuf。
// 
// go:notinheap 
type stackWorkBuf struct {
	stackWorkBufHdr
	obj [(_WorkbufSize - unsafe.Sizeof(stackWorkBufHdr{})) / goarch.PtrSize]uintptr
}

// 由于问题#14620，标题声明必须在上述buf声明之后。
// 
// go:notinheap 
type stackWorkBufHdr struct {
	workbufhdr
	next *stackWorkBuf // 工作列表
	// 注意：理论上我们可以重新调整lfnode的用途。下一个作为下一个指针。
	// 这会节省一个单词，但这可能不值得破坏打开的
	// lfnode API。
}

// 在goroutine堆栈上找到的堆栈对象的缓冲区。
// 必须小于或等于workbuf。
// 
// go:notinheap 
type stackObjectBuf struct {
	stackObjectBufHdr
	obj [(_WorkbufSize - unsafe.Sizeof(stackObjectBufHdr{})) / unsafe.Sizeof(stackObject{})]stackObject
}

// go:notinheap 
type stackObjectBufHdr struct {
	workbufhdr
	next *stackObjectBuf
}

func init() {
	if unsafe.Sizeof(stackWorkBuf{}) > unsafe.Sizeof(workbuf{}) {
		panic("stackWorkBuf too big")
	}
	if unsafe.Sizeof(stackObjectBuf{}) > unsafe.Sizeof(workbuf{}) {
		panic("stackObjectBuf too big")
	}
}

// stackObject表示堆栈上的变量，该变量的地址为
// 。
// 
// go:notinheap 
type stackObject struct {
	off   uint32             // 堆栈上方的偏移量。lo 
	size  uint32             // 对象大小
	r     *stackObjectRecord // 对象信息（用于ptr/NONTTR位）。如果对象已被扫描，则为零。
	left  *stackObject       // 地址较低的对象
	right *stackObject       // 地址较高的对象
}

// obj。r=r，但没有写障碍。
// go:nowritebarrier 
func (obj *stackObject) setRecord(r *stackObjectRecord) {
	// 类型的堆栈对象始终位于只读内存中，而不是堆中。
	// 所以不使用写屏障是可以的。
	*(*uintptr)(unsafe.Pointer(&obj.r)) = uintptr(unsafe.Pointer(r))
}

// stackScanState跟踪goroutine的GC遍历期间使用的状态。
type stackScanState struct {
	cache pcvalueCache

	// 堆栈限制
	stack stack

	// 保守表示必须保守扫描下一帧。
	// 这只适用于异步安全点的最内层帧。
	conservative bool

	// buf包含指向堆栈对象的一组可能的指针。
	// 组织为后进先出缓冲区链接列表。
	// 除头部缓冲区外，所有缓冲区都已满。
	buf     *stackWorkBuf
	freeBuf *stackWorkBuf // 为分配保留大约一个可用缓冲区

	// cbuf包含指向堆栈对象的保守指针。如果
	// 指向堆栈对象的所有指针都是通过
	// 保守扫描获得的，那么堆栈对象可能是死的
	// 并且可能包含死指针，因此必须对其进行防御扫描。
	cbuf *stackWorkBuf

	// 堆栈对象列表
	// 对象的地址顺序在增加。
	head  *stackObjectBuf
	tail  *stackObjectBuf
	nobjs int

	// 用于通过地址快速查找对象的二叉树的根
	// 由buildIndex初始化。
	root *stackObject
}

// 将p添加为指向堆栈对象的潜在指针。
// p必须是堆栈地址。
func (s *stackScanState) putPtr(p uintptr, conservative bool) {
	if p < s.stack.lo || p >= s.stack.hi {
		throw("address not a stack address")
	}
	head := &s.buf
	if conservative {
		head = &s.cbuf
	}
	buf := *head
	if buf == nil {
		// 初始设置。
		buf = (*stackWorkBuf)(unsafe.Pointer(getempty()))
		buf.nobj = 0
		buf.next = nil
		*head = buf
	} else if buf.nobj == len(buf.obj) {
		if s.freeBuf != nil {
			buf = s.freeBuf
			s.freeBuf = nil
		} else {
			buf = (*stackWorkBuf)(unsafe.Pointer(getempty()))
		}
		buf.nobj = 0
		buf.next = *head
		*head = buf
	}
	buf.obj[buf.nobj] = p
	buf.nobj++
}

// 删除并返回指向堆栈对象的潜在指针。
// 如果没有更多可用的指针，则返回0。
// 
// 这更喜欢非保守指针，所以我们可以精确地扫描堆栈对象
// 如果有任何指向它们的非保守指针。
func (s *stackScanState) getPtr() (p uintptr, conservative bool) {
	for _, head := range []**stackWorkBuf{&s.buf, &s.cbuf} {
		buf := *head
		if buf == nil {
			// 从来没有任何数据。
			continue
		}
		if buf.nobj == 0 {
			if s.freeBuf != nil {
				// 免费的旧freeBuf。
				putempty((*workbuf)(unsafe.Pointer(s.freeBuf)))
			}
			// 将buf移到freeBuf。
			s.freeBuf = buf
			buf = buf.next
			*head = buf
			if buf == nil {
				// 此列表中没有更多数据。
				continue
			}
		}
		buf.nobj--
		return buf.obj[buf.nobj], head == &s.cbuf
	}
	// 两个列表中都没有更多数据。
	if s.freeBuf != nil {
		putempty((*workbuf)(unsafe.Pointer(s.freeBuf)))
		s.freeBuf = nil
	}
	return 0, false
}

// addObject在addr向堆栈对象集添加类型为typ的堆栈对象。
func (s *stackScanState) addObject(addr uintptr, r *stackObjectRecord) {
	x := s.tail
	if x == nil {
		// 初始设置
		x = (*stackObjectBuf)(unsafe.Pointer(getempty()))
		x.next = nil
		s.head = x
		s.tail = x
	}
	if x.nobj > 0 && uint32(addr-s.stack.lo) < x.obj[x.nobj-1].off+x.obj[x.nobj-1].size {
		throw("objects added out of order or overlapping")
	}
	if x.nobj == len(x.obj) {
		// 完全缓冲区-分配一个新缓冲区，添加到链表末尾
		y := (*stackObjectBuf)(unsafe.Pointer(getempty()))
		y.next = nil
		x.next = y
		s.tail = y
		x = y
	}
	obj := &x.obj[x.nobj]
	x.nobj++
	obj.off = uint32(addr - s.stack.lo)
	obj.size = uint32(r.size)
	obj.setRecord(r)
	// obj。左和右。在使用之前，将由buildIndex初始化right。
	s.nobjs++
}

// buildIndex将s.root初始化为二叉搜索树。
// 应该在所有addObject调用之后调用，但在
// 任何findObject调用之前调用。
func (s *stackScanState) buildIndex() {
	s.root, _, _ = binarySearchTree(s.head, 0, s.nobjs)
}

// 使用列表中的n个对象构建二叉搜索树
// x.obj[idx]，x.obj[idx+1]。。。，x、 下一个。obj[0]。。。
// 返回该树的根，以及x.obj[idx]之后第n个对象的buf+idx。
// /（二元搜索树中未包含的第一个对象。）
// 如果n==0，则返回nil，x。
func binarySearchTree(x *stackObjectBuf, idx int, n int) (root *stackObject, restBuf *stackObjectBuf, restIdx int) {
	if n == 0 {
		return nil, x, idx
	}
	var left, right *stackObject
	left, x, idx = binarySearchTree(x, idx, n/2)
	root = &x.obj[idx]
	idx++
	if idx == len(x.obj) {
		x = x.next
		idx = 0
	}
	right, x, idx = binarySearchTree(x, idx, n-n/2-1)
	root.left = left
	root.right = right
	return root, x, idx
}

// findObject返回包含地址a的堆栈对象（如果有）。
// 以前一定调用过buildIndex。
func (s *stackScanState) findObject(a uintptr) *stackObject {
	off := uint32(a - s.stack.lo)
	obj := s.root
	for {
		if obj == nil {
			return nil
		}
		if off < obj.off {
			obj = obj.left
			continue
		}
		if off >= obj.off+obj.size {
			obj = obj.right
			continue
		}
		return obj
	}
}
